オーダー order notation
アルゴリズムの時間計算量の評価を簡単化する記法（Bachmann-Landau 記法）
𝑂 記法 … 計算量の上界
Ω 記法 … 計算量の下界
Θ 記法 … 計算量の上界と下界
※その他に 𝑜 記法や𝜔 記法がある．
問題の入力サイズが十分に大きいときの（極限における），
入力サイズの増加に対する時間計算量の増加の程度を別の関数を目安にして記述
処理がどれくらい時間がかかるのかを表したもの
𝑂 記法（Big-O notation）が一般的
関数の漸近的上界を表すオーダー記法
例:
多項式オーダー（polynomial order）
table:order
表記 意味 例 問題
O(1) 定数時間 処理時間がデータ量に依存しない O(k**n) 指数時間 𝑛 個の要素の取り出し方の全組合せを調べる 集合分割問題など O(n!) 階乗時間 𝑛 の階乗に比例した時間がかかる 巡回セールスマン問題の総当たりによる解法など 参考